// 文件名：multimap_inverted_index.cpp
// 目的：以 std::multimap 实现简单倒排索引：term -> docID，支持按词项查询所有出现的文档。
// 设计：
//   - multimap<string,int> 允许同一 term 映射到多个 docID；
//   - equal_range(term) 一次性获取该 term 的所有倒排记录；
//   - 查询函数 query(term) 收集并打印所有文档 ID（演示用途）。
// 扩展建议：
//   - 可为 postings 去重并排序；
//   - 为高效交并集检索，生产系统会使用压缩倒排表（如跳表、位图、跳跃表段等）。
#include <iostream>
#include <map>
#include <string>
#include <vector>

int main() {
    std::multimap<std::string, int> index = {
        {"search", 1}, {"engine", 1}, {"distributed", 1},
        {"search", 2}, {"index", 2}, {"engine", 2},
        {"search", 3}, {"ranking", 3}
    };

    // 查询某个词项的所有文档编号
    auto query = [&](const std::string& term) {
        auto [begin, end] = index.equal_range(term); // O(log N) 定位，O(K) 遍历
        std::vector<int> postings;
        for (auto it = begin; it != end; ++it) {
            postings.push_back(it->second);
        }
        std::cout << "Term \"" << term << "\" appears in documents:";
        if (postings.empty()) {
            std::cout << " (none)\n";
        } else {
            for (int id : postings) std::cout << ' ' << id;
            std::cout << '\n';
        }
    };

    query("search");
    query("engine");
    query("ranking");
    query("missing");
    return 0;
}